Teaching Recursion
A few weeks ago I ran into this tweet.
The same tweet – as the perfect illustrative homage to the concept – was retweeted thousands of times with the same message quoted within each new tweet. This got me thinking about the complex nature of this specific concept in computer science. For students who master and effectively use looping structures for a long time before being introduced to recursion, it may seem like an extension to loops, albeit a pointless one. The question “When will I ever use this?” or “Why can't we just use a loop instead? Isn’t that better for memory?” is commonplace. (As an aside: I did run into an interesting 1999 research paper that argues that recursion as a concept should be taught before iterations. In fact, a computing teacher in Malaysia works with recursive methods to introduce functions via data input validation with his students.)
A few days ago I ran into another recursion related tweet.
Despite the understandably cynical take on the list, there are a few interesting examples on it of how recursion can be understood and appreciated by students. To educate myself on the state of things, I explored a range of resources, including some unplugged and hands-on activities that came my way.
But before we get into the how, let us take a quick look at the why, since anything that is worth learning needs a context. If we expect students to appreciate a difficult concept, having a strong (and interesting!) rationale for using it is critical. Who would want to learn something that is neither engaging nor useful? If teachers do not then students definitely will not. So let us try to address that for recursion first.
The Why
The primary reasons recursion has a role and presence in computing:
1. To reduce the complexity of a problem
There are some problems so complex that an iterative solution cannot fix. Traversing a tree structure is a common example cited for this, given its dynamic nature. Recursion seems simpler for such problems purely because of its reductive nature.
This Medium article advocates for recursion by demonstrating an array sum and tree navigation example. For the array sum, the argument can be made that an array can easily be traversed with a loop, without need for recursion, thus condensing the problem so that it meets a natural end (e.g., supplying a function with a lesser value so that eventually it stops). It's an approach worth noting. But as far as the tree is concerned, navigating in different directions of a data structure is most efficient with recursion. The dynamic nature of a recursive method allows for movement up, down, left and right whereas a looping structure usually goes one way at a time (hence needing more workflows to accomplish something as complex as tree traversal).
A question that may arise at this point is: why do we need trees? But tree structures in software development have a wide range of applications. File compression and network routing algorithms use tree structures to hold and process data. So if the focus is on high performance algorithms, then recognizing the role of recursion is equally vital.
2. To create shorter (and possibly cleaner) code
Shorter does not always mean better, I know. This is especially true for recursion. Even though a function may contain only 4-5 lines, it can be hard to read, or bad at managing memory. Even for seasoned developers and experienced teachers, tracing a recursive method for the first time requires time and focus. All concepts need this, but even more so for something as layered as recursion.
To illustrate from a coding perspective, let us take a simple example where a function needs to build a word by collecting characters sent to it via an array. First, we will look at the looping version of it. (This is meant to be a representation, so actual syntax/approach may vary.)
- function buildWord(char[] array) {
- String word; // to hold final word
- int N = array.size() // to know how far we loop
- for i in 0 to N
- loop
- word = word + array[i] // attach each character
- end loop
- return word // return final word back
- }
Now, let us consider a recursive method that does the same thing.
- function buildWord(char[] array) {
- if (array.size()==1) return array[0]; // base case for termination
- return array[0] + buildWord(array minus first character) // recursive case to keep going
- }
Notice how the base case (which terminates the function) comes first. If the array has only 1 character, it returns just that and it is done. Else, it will attach the character. So, if the array had ['h', 'e', 'y'] originally, the return calls would be:
- 'h' + buildWord(['e','y'])
- 'h' + ('e' + buildWord(['y'])) // this makes the base case true
- 'h' + ('e' + ('y')) // values stored in memory wrapped up
- 'h' + ('ey')
- 'hey'
While this may seem like an overly simple rationale to use a recursive method, the idea is to build a solution that can do more with less. Recursive methods are powerful particularly when it comes to handling dynamic and large data structures. Then there is the matter of memory management. Quality trumps quantity, but not at the cost of needless memory overheads.
You will find plenty of literature on the web that sums up the differences between iterations and recursion – such as here, here, here and here. At the end of the day the problem at hand will decide which approach is best.
The How
Inspired by some of my recent conversations with the SEACSTA group of educators who have tried different methods in their classrooms surrounding this topic, I tried to collect some resources that could help trigger both the mindset and scaffold the learning for both teachers and students.
Hands-on Activities
In addition to the popular Fibonacci sequence, and Factorial, Hanoi Towers or Binary Search examples, here is a list of other activities I found.
Pass the Candy: Students get into groups and 3-4 and get N candies to start with. Then they halve it and pass it on to the partner on their left. Tracing the candy passes makes for some interesting results.
Frogs in a Pond: A short collection of activities that allow students to explore the idea of recursive processing using unplugged approaches.
LEGO Towers: Part of this research paper contains a LEGO tower based word activity that uses recursion.
Khan Academy Russian Doll: Tutorial that highlights different aspects of recursion with some word challenges.
Robot Maze Challenge: A robot and maze activity replicable as hands on before the coding element.
The Cat in the Hat Comes Back: A classic by Dr. Seuss, the story of cats A to Z is a good activity to read aloud and enact in class.
Exploring Recursion Through Art: Activities with nested drawings.
The Where
Finally, a quick list of other interesting resources I found that address different aspects of recursion.
Insights and Conflicts in discussing Recursion: Case Study
A Structured Approach to Teaching Recursion Using Cargo-Bot
NCSSM and North Carolina Public Schools: Recursion lessons
FreeCodeCamp – Visual guide to recursion
Recursion – How to overflow the stack and how not to
Explain Recursion Like I’m Five
Explanation and Example of Simple Recursion
How do I explain “recursion” to an 8-year-old kid?
Christmas Computing – Some Xmas themed unplugged activities
Teach Recursion with AlgoBot
Problem Solving with Algorithms and Data Structures using Python
The bottom line
Recursions are always somewhat complex. Like any programming construct, the more time one spends with it, the better one can get at it. One of the biggest challenges students have is to be presented unfamiliar code or an algorithm and be asked to trace it. Some of the activities above encourage using printed trace tables to help in following the algorithm to see what it is doing.
I also found this lovely little piece from a StackOverflow question on recursion. I thought it had a place here.
This piece was originally published at Compute Thought.
